﻿/*
    * Designer:       Virgil  
    * Description:    The algorithm of the solver
    * Created:         06/07/2010
    * History:
==============================================================
    * Author      DateTime        Alter Description
==============================================================
    */
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
using System.IO;
using System.Collections.Specialized;

namespace SudokuSolver
{
    public class SampleSolver : SudokuWPF.ISudokuSolver
    {
        #region ISudokuSolver 成员

        public string Name
        {
            get { return "递归算法实现"; }
        }

        public string Description
        {
            get { return "递归方法实现，在递归前进行有限递推。4x4可以瞬间生成，而9x9需花费较长时间！"; }
        }

        public string Author
        {
            get { return "蔡春生"; }
        }

        public bool Solve(ref int?[,] board)
        {
            //System.Diagnostics.Debug.WriteLine("Begin");
            int size = board.GetLength(0);       //棋盘大小
            List<int>[,] possible = new List<int>[size, size]; //存放候选数的数组,记录所有未确定数字的可能性
            //记录所有数格的可能性,确定possible矩阵列表的值，如果已有值的将首元素放入列表第一个
            for (int r = 0; r < size; r++)
            {
                for (int c = 0; c < size; c++)
                {
                    possible[r, c] = new List<int>();
                    if (board[r, c].HasValue)
                    {
                        possible[r, c].Add(Math.Abs(board[r, c].Value));//如果数格已经有值，将其添加到列表
                    }
                    else
                    {
                        for (int i = 1; i <= board.GetLength(0); i++)   //如果没有,则将1-9当做候选数都添加到列表
                        {
                            possible[r, c].Add(i);
                        }
                    }
                }
            }
            bool ret = RecursiveSolve(ref possible);//调用递归算法求解看是否有答案
            if (ret)     //如果有解，将possible矩阵列表的第一个元素赋值给board
            {
                for (int r = 0; r < size; r++)
                {
                    for (int c = 0; c < size; c++)
                    {
                        if (!board[r, c].HasValue || board[r, c].Value > 0)
                            board[r, c] = possible[r, c][0];       //数组保存到最终结果board数组中
                    }
                }
            }
            //if (!ret) System.Diagnostics.Debug.WriteLine("Fail");
            //System.Diagnostics.Debug.WriteLine("End");
            return ret;

        }

        #endregion
        //递归算法
        bool RecursiveSolve(ref List<int>[,] board)
        {
            int size = board.GetLength(0);       //棋盘大小
            int blocksize = (int)Math.Sqrt(size);//宫格大小
            bool changeMade = false;            //标识数组是否改变
            #region 有限递推
            //有限递推，执行一次就可能确定下一些原来没有确定的数字，那么此时，原始的数据的值必然也会变动！因为确定的数字越多，某些位置可能的数字就越少。那么就应该在次执行次过程修订矩阵，而修订之后可能又会出现一些只有一种可能性的位置，那么就在执行次过程了。于是如此循环下去，就能最大限度地确定下有题目本身含义与规则而确定下的内容。当changeMade值为假，有限递推结束。
            do
            {
                changeMade = false;
                //遍历行，除去当前行已有的数字
                for (int r = 0; r < size; r++)
                {
                    List<int> toRemove = new List<int>();   //保存排除后的结果
                    for (int c = 0; c < size; c++)
                    {
                        if (board[r, c].Count == 1) toRemove.Add(board[r, c][0]);   //只剩一个项目时,将其放到数组的首元素
                    }
                    for (int c = 0; c < size; c++)
                    {
                        if (board[r, c].Count > 1)
                        {
                            foreach (int i in toRemove)
                            {
                                if (board[r, c].Remove(i))
                                    changeMade = true;
                            }
                            //if (board[r, c].Count == 1)
                            //   System.Diagnostics.Debug.WriteLine("Set: " + board[r, c][0] + " [" + r + ", " + c + "]");

                        }
                    }
                }
                //遍历列
                for (int c = 0; c < size; c++)
                {
                    List<int> toRemove = new List<int>();
                    for (int r = 0; r < size; r++)
                    {
                        if (board[r, c].Count == 1) toRemove.Add(board[r, c][0]);
                    }
                    for (int r = 0; r < size; r++)
                    {
                        if (board[r, c].Count > 1)
                        {
                            foreach (int i in toRemove)
                            {
                                if (board[r, c].Remove(i))
                                    changeMade = true;
                            }
                            // if (board[r, c].Count == 1)
                            //    System.Diagnostics.Debug.WriteLine("Set: " + board[r, c][0] + " [" + r + ", " + c + "]");

                        }
                    }
                }
                //遍历宫格
                for (int r = 0; r < size - blocksize; r += blocksize)
                {
                    for (int c = 0; c < size - blocksize; c += blocksize)
                    {
                        List<int> toRemove = new List<int>();
                        for (int br = 0; br < blocksize; br++)
                        {
                            for (int bc = 0; bc < blocksize; bc++)
                            {
                                if (board[r + br, c + bc].Count == 1) toRemove.Add(board[r + br, c + bc][0]);
                            }
                        }
                        for (int br = 0; br < blocksize; br++)
                        {
                            for (int bc = 0; bc < blocksize; bc++)
                            {
                                if (board[r + br, c + bc].Count > 1)
                                {
                                    foreach (int i in toRemove)
                                    {
                                        if (board[r + br, c + bc].Remove(i))
                                            changeMade = true;
                                    }
                                    //if (board[r + br, c + bc].Count == 1)
                                    //   System.Diagnostics.Debug.WriteLine("Set: " + board[r + br, c + bc][0] + " [" + (r + br) + ", " + (c + bc) + "]");
                                }
                            }
                        }
                    }
                }
            }
            while (changeMade);
            #endregion
            //寻找有多以一个候选数的数格
            int minr = 0, minc = 0;
            int min = size;
            for (int r = 0; r < size; r++)
            {
                for (int c = 0; c < size; c++)
                {
                    if (board[r, c].Count == 0)
                    {
                        return false;
                    }
                    else if (board[r, c].Count > 1 && board[r, c].Count < size)
                    {
                        minr = r;
                        minc = c;
                        size = board[r, c].Count;
                    }
                }
            }
            //当所有的数格都只有一个候选数的情况
            //if (guessCount > 1) return true;
            if (board[minr, minc].Count == 1) //只有数独一个数，验证
            {
                return Validate(board);
            }
            #region 选取候选数进行猜想
            Random rnd = new Random();
            List<int> cell = board[minr, minc];
            int baseidx = rnd.Next(cell.Count); //随机选取候选数，作为假设值，进行猜想

            //通过深度拷贝进行递归，无法确定者，则应回到前一位置，修改其假设值
            for (int i = 0; i < cell.Count; i++)
            {
                List<int>[,] c = DeepCopy(board);   //深度拷贝
                c[minr, minc].Clear();
                c[minr, minc].Add(cell[baseidx]);     //将其作为正确的数进行猜想

                //System.Diagnostics.Debug.WriteLine("Guess: " + i + " [" + minr + ", " + minc + "]");
                //递归调用
                if (RecursiveSolve(ref c))
                {
                    board = c;
                    return true; 
                }
                /*
                else
                {
                    System.Diagnostics.Debug.WriteLine("Failed Guess: " + i + " [" + minr + ", " + minc + "]");
                }
                 */
                baseidx++;
                if (baseidx == cell.Count) baseidx = 0;
            }
            #endregion
            return false;
        }
        //标识已经确定下来的数格，已经确定为1
        bool Validate(List<int>[,] board)
        {
            int size = board.GetLength(0);
            int blocksize = (int)Math.Sqrt(size);
            for (int r = 0; r < size; r++)
            {
                bool[] used = new bool[size];
                for (int c = 0; c < size; c++)
                {
                    if (used[board[r, c][0] - 1])
                    {
                        return false;
                    }
                    else
                    {
                        used[board[r, c][0] - 1] = true;
                    }
                }
            }
            for (int c = 0; c < size; c++)
            {
                bool[] used = new bool[size];
                for (int r = 0; r < size; r++)
                {
                    if (used[board[r, c][0] - 1])
                    {
                        return false;
                    }
                    else
                    {
                        used[board[r, c][0] - 1] = true;
                    }
                }
            }
            for (int r = 0; r < size - blocksize; r += blocksize)
            {
                for (int c = 0; c < size - blocksize; c += blocksize)
                {
                    bool[] used = new bool[size];
                    for (int br = 0; br < blocksize; br++)
                    {
                        for (int bc = 0; bc < blocksize; bc++)
                        {
                            if (used[board[br + r, bc + c][0] - 1])
                            {
                                return false;
                            }
                            else
                            {
                                used[board[br + r, bc + c][0] - 1] = true;
                            }
                        }
                    }
                }
            }
            return true;
        }
        //深度拷贝，将当前对象的所有字段进行执行逐位复制并支持递归
        List<int>[,] DeepCopy(List<int>[,] board)
        {
            List<int>[,] n = board.Clone() as List<int>[,];
            for (int a = 0; a < n.GetLength(0); a++)
            {
                for (int b = 0; b < n.GetLength(1); b++)
                {
                    n[a, b] = new List<int>(n[a, b]);
                }
            }
            return n;
        }
    }
}